home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / Mesa-1.2.1 / src-glu / polytest.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-07-05  |  26.1 KB  |  1,027 lines
  1. /* polytest.c */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  1.2
  6.  * Copyright (C) 1995  Brian Paul  (brianp@ssec.wisc.edu)
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25. $Id: polytest.c,v 1.4 1995/06/09 16:41:07 brianp Exp $
  26.  
  27. $Log: polytest.c,v $
  28.  * Revision 1.4  1995/06/09  16:41:07  brianp
  29.  * renamed as polytest.c
  30.  *
  31.  * Revision 1.3  1995/05/23  17:37:48  brianp
  32.  * added #ifndef NULL ...
  33.  *
  34.  * Revision 1.2  1995/05/22  16:56:20  brianp
  35.  * Release 1.2
  36.  *
  37.  * Revision 1.1  1995/04/28  16:20:28  brianp
  38.  * Initial revision
  39.  *
  40.  */
  41.  
  42.  
  43. /*
  44.  * This file is part of the polygon tesselation code contributed by
  45.  * Bogdan Sikorski
  46.  */
  47.  
  48.  
  49. #include "tess.h"
  50. #include <math.h>
  51. #include <stdlib.h>
  52.  
  53. #ifndef NULL
  54. #  define NULL 0
  55. #endif
  56.  
  57.  
  58. static GLUenum store_polygon_as_contour(GLUtriangulatorObj *);
  59. static void free_current_polygon(tess_polygon *);
  60. static void prepare_projection_info(GLUtriangulatorObj *);
  61. static GLdouble twice_the_polygon_area(tess_vertex *,tess_vertex *);
  62. static GLUenum verify_edge_vertex_intersections(GLUtriangulatorObj *);
  63. void tess_find_contour_hierarchies(GLUtriangulatorObj *);
  64. static GLUenum test_for_overlapping_contours(GLUtriangulatorObj *);
  65. static GLUenum contours_overlap(tess_contour *, tess_polygon *);
  66. static GLUenum is_contour_contained_in(tess_contour *,tess_contour *);
  67. static void add_new_exterior(GLUtriangulatorObj *,tess_contour *);
  68. static void add_new_interior(GLUtriangulatorObj *,tess_contour *,
  69.     tess_contour *);
  70. static void add_interior_with_hierarchy_check(GLUtriangulatorObj *,
  71.     tess_contour *,tess_contour *);
  72. static void reverse_hierarchy_and_add_exterior(GLUtriangulatorObj *,
  73.     tess_contour *,tess_contour *);
  74. static GLboolean point_in_polygon(tess_contour *,GLdouble,GLdouble);
  75. static void shift_interior_to_exterior(GLUtriangulatorObj *,tess_contour *);
  76. static void add_exterior_with_check(GLUtriangulatorObj *,tess_contour *,
  77.     tess_contour *);
  78. static GLUenum cut_out_hole(GLUtriangulatorObj *,tess_contour *,
  79.     tess_contour *);
  80. static GLUenum merge_hole_with_contour(GLUtriangulatorObj *,
  81.     tess_contour *,tess_contour *,tess_vertex *,
  82.     tess_vertex *);
  83.  
  84. static GLUenum
  85. find_normal(GLUtriangulatorObj *tobj)
  86. {
  87.     tess_polygon *polygon=tobj->current_polygon;
  88.     tess_vertex *va,*vb,*vc;
  89.     GLdouble A,B,C;
  90.     GLdouble A0,A1,A2,B0,B1,B2;
  91.  
  92.     va=polygon->vertices;
  93.     vb=va->next;
  94.     A0=vb->location[0]-va->location[0];
  95.     A1=vb->location[1]-va->location[1];
  96.     A2=vb->location[2]-va->location[2];
  97.     for(vc=vb->next;vc!=va;vc=vc->next)
  98.     {
  99.         B0=vc->location[0]-va->location[0];
  100.         B1=vc->location[1]-va->location[1];
  101.         B2=vc->location[2]-va->location[2];
  102.         A=A1*B2-A2*B1;
  103.         B=A2*B0-A0*B2;
  104.         C=A0*B1-A1*B0;
  105.         if(fabs(A)>EPSILON || fabs(B)>EPSILON || fabs(C)>EPSILON)
  106.         {
  107.             polygon->A=A;
  108.             polygon->B=B;
  109.             polygon->C=C;
  110.             polygon->D= -A*va->location[0]-B*va->location[1]-C*va->location[2];
  111.             return GLU_NO_ERROR;
  112.         }
  113.     }
  114.     tess_call_user_error(tobj,GLU_TESS_ERROR7);
  115.     return GLU_ERROR;
  116. }
  117.  
  118. void
  119. tess_test_polygon( GLUtriangulatorObj *tobj )
  120. {
  121.     tess_polygon *polygon=tobj->current_polygon;
  122.  
  123.     /* any vertices defined? */
  124.     if(polygon->vertex_cnt<3)
  125.     {
  126.         free_current_polygon(polygon);
  127.         return;
  128.     }
  129.     /* wrap pointers */
  130.     polygon->last_vertex->next=polygon->vertices;
  131.     polygon->vertices->previous=polygon->last_vertex;
  132.     /* determine the normal */
  133.     if(find_normal(tobj)==GLU_ERROR)
  134.         return;
  135.     /* compare the normals of previously defined contours and this one */
  136.     /* first contour define ? */
  137.     if(tobj->contours==NULL)
  138.     {
  139.         tobj->A=polygon->A;
  140.         tobj->B=polygon->B;
  141.         tobj->C=polygon->C;
  142.         tobj->D=polygon->D;
  143.         /* determine the best projection to use */
  144.         if(fabs(polygon->A) > fabs(polygon->B))
  145.             if(fabs(polygon->A) > fabs(polygon->C))
  146.                 tobj->projection=OYZ;
  147.             else
  148.                 tobj->projection=OXY;
  149.         else
  150.             if(fabs(polygon->B) > fabs(polygon->C))
  151.                 tobj->projection=OXZ;
  152.             else
  153.                 tobj->projection=OXY;
  154.     }
  155.     else
  156.     {
  157.         GLdouble a[3],b[3];
  158.         tess_vertex *vertex=polygon->vertices;
  159.  
  160.         a[0]=tobj->A;
  161.         a[1]=tobj->B;
  162.         a[2]=tobj->C;
  163.         b[0]=polygon->A;
  164.         b[1]=polygon->B;
  165.         b[2]=polygon->C;
  166.  
  167.         /* compare the normals */
  168.         if( fabs(a[1]*b[2]-a[2]*b[1]) > EPSILON ||
  169.             fabs(a[2]*b[0]-a[0]*b[2]) > EPSILON ||
  170.             fabs(a[0]*b[1]-a[1]*b[0]) > EPSILON)
  171.         {
  172.             /* not coplanar */
  173.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  174.             return;
  175.         }
  176.         /* the normals are parallel - test for plane equation */
  177.         if(fabs(a[0]*vertex->location[0]+a[1]*vertex->location[1]+
  178.             a[2]*vertex->location[2]+tobj->D) > EPSILON)
  179.         {
  180.             /* not the same plane */
  181.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  182.             return;
  183.         }
  184.     }
  185.     prepare_projection_info(tobj);
  186.     if(verify_edge_vertex_intersections(tobj)==GLU_ERROR)
  187.         return;
  188.     if(test_for_overlapping_contours(tobj)==GLU_ERROR)
  189.         return;
  190.     if(store_polygon_as_contour(tobj)==GLU_ERROR)
  191.         return;
  192. }
  193.  
  194. static GLUenum test_for_overlapping_contours(GLUtriangulatorObj *tobj)
  195. {
  196.     tess_contour *contour;
  197.     tess_polygon *polygon;
  198.  
  199.     polygon=tobj->current_polygon;
  200.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  201.         if(contours_overlap(contour,polygon)!=GLU_NO_ERROR)
  202.         {
  203.             tess_call_user_error(tobj,GLU_TESS_ERROR5);
  204.             return GLU_ERROR;
  205.         }
  206.     return GLU_NO_ERROR;
  207. }
  208.  
  209. static GLUenum store_polygon_as_contour(GLUtriangulatorObj *tobj)
  210. {
  211.     tess_polygon *polygon=tobj->current_polygon;
  212.     tess_contour *contour=tobj->contours;
  213.  
  214.     /* the first contour defined */
  215.     if(contour==NULL)
  216.     {
  217.         if((contour=(tess_contour *)malloc(
  218.             sizeof(tess_contour)))==NULL)
  219.         {
  220.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  221.             free_current_polygon(polygon);
  222.             return GLU_ERROR;
  223.         }
  224.         tobj->contours=tobj->last_contour=contour;
  225.         contour->next=contour->previous=NULL;
  226.     }
  227.     else
  228.     {
  229.         if((contour=(tess_contour *)malloc(
  230.             sizeof(tess_contour)))==NULL)
  231.         {
  232.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  233.             free_current_polygon(polygon);
  234.             return GLU_ERROR;
  235.         }
  236.         contour->previous=tobj->last_contour;
  237.         tobj->last_contour->next=contour;
  238.         tobj->last_contour=contour;
  239.         contour->next=NULL;
  240.     }
  241.     /* mark all vertices in new contour as not special */
  242.     /* and all are boundary edges */
  243.     {
  244.         tess_vertex *vertex;
  245.         GLuint vertex_cnt,i;
  246.  
  247.         for(vertex=polygon->vertices , i=0 , vertex_cnt=polygon->vertex_cnt;
  248.             i<vertex_cnt;
  249.             vertex=vertex->next , i++)
  250.         {
  251.             vertex->shadow_vertex=NULL;
  252.             vertex->edge_flag=GL_TRUE;
  253.         }
  254.     }
  255.     contour->vertex_cnt=polygon->vertex_cnt;
  256.     contour->area=polygon->area;
  257.     contour->orientation=polygon->orientation;
  258.     contour->type=GLU_UNKNOWN;
  259.     contour->vertices=polygon->vertices;
  260.     contour->last_vertex=polygon->last_vertex;
  261.     polygon->vertices=polygon->last_vertex=NULL;
  262.     polygon->vertex_cnt=0;
  263.     ++(tobj->contour_cnt);
  264.     return GLU_NO_ERROR;
  265. }
  266.  
  267. static void free_current_polygon(tess_polygon *polygon)
  268. {
  269.     tess_vertex *vertex,*vertex_tmp;
  270.  
  271.     /* free current_polygon structures */
  272.     for(vertex=polygon->vertices;vertex!=polygon->last_vertex;)
  273.     {
  274.         vertex_tmp=vertex->next;
  275.         free(vertex);
  276.         vertex=vertex_tmp;
  277.     }
  278.     polygon->vertices=polygon->last_vertex=NULL;
  279.     polygon->vertex_cnt=0;
  280. }
  281.  
  282. static void prepare_projection_info(GLUtriangulatorObj *tobj)
  283. {
  284.     tess_polygon *polygon=tobj->current_polygon;
  285.     tess_vertex *vertex,*last_vertex_ptr;
  286.     GLdouble area;
  287.  
  288.     last_vertex_ptr=polygon->last_vertex;
  289.     switch(tobj->projection)
  290.     {
  291.         case OXY:
  292.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  293.                 vertex=vertex->next)
  294.             {
  295.                 vertex->x=vertex->location[0];
  296.                 vertex->y=vertex->location[1];
  297.             }
  298.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  299.             last_vertex_ptr->y=last_vertex_ptr->location[1];
  300.             break;
  301.         case OXZ:
  302.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  303.                 vertex=vertex->next)
  304.             {
  305.                 vertex->x=vertex->location[0];
  306.                 vertex->y=vertex->location[2];
  307.             }
  308.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  309.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  310.             break;
  311.         case OYZ:
  312.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  313.                 vertex=vertex->next)
  314.             {
  315.                 vertex->x=vertex->location[1];
  316.                 vertex->y=vertex->location[2];
  317.             }
  318.             last_vertex_ptr->x=last_vertex_ptr->location[1];
  319.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  320.             break;
  321.     }
  322.     area=twice_the_polygon_area(polygon->vertices,polygon->last_vertex);
  323.     if(area >= 0.0)
  324.     {
  325.         polygon->orientation=GLU_CCW;
  326.         polygon->area=area;
  327.     }
  328.     else
  329.     {
  330.         polygon->orientation=GLU_CW;
  331.         polygon->area= -area;
  332.     }
  333. }
  334.  
  335. static GLdouble twice_the_polygon_area(tess_vertex *vertex,
  336.     tess_vertex *last_vertex)
  337. {
  338.     tess_vertex *next;
  339.     GLdouble area,x,y;
  340.  
  341.     area=0.0;
  342.     x=vertex->x;
  343.     y=vertex->y;
  344.     vertex=vertex->next;
  345.     for(; vertex!=last_vertex; vertex=vertex->next)
  346.     {
  347.         next=vertex->next;
  348.         area+=(vertex->x - x)*(next->y - y) - (vertex->y - y)*(next->x - x);
  349.     }
  350.     return area;
  351. }
  352.  
  353. /* test if edges ab and cd intersect */
  354. /* if not return GLU_NO_ERROR, else if cross return GLU_TESS_ERROR8, */
  355. /* else if adjacent return GLU_TESS_ERROR4 */
  356. static GLUenum edge_edge_intersect(
  357.     tess_vertex *a,
  358.     tess_vertex *b,
  359.     tess_vertex *c,
  360.     tess_vertex *d)
  361. {
  362.     GLdouble denom,r,s;
  363.     GLdouble xba,ydc,yba,xdc,yac,xac;
  364.  
  365.     xba=b->x - a->x;
  366.     yba=b->y - a->y;
  367.     xdc=d->x - c->x;
  368.     ydc=d->y - c->y;
  369.     xac=a->x - c->x;
  370.     yac=a->y - c->y;
  371.     denom= xba*ydc - yba*xdc;
  372.     r = yac*xdc - xac*ydc;
  373.     /* parallel? */
  374.     if(fabs(denom) < EPSILON)
  375.     {
  376.         if(fabs(r) < EPSILON)
  377.         {
  378.             /* colinear */
  379.             if(fabs(xba) < EPSILON)
  380.             {
  381.                 /* compare the Y coordinate */
  382.                 if(yba > 0.0)
  383.                 {
  384.                     if((fabs(a->y - c->y)<EPSILON && fabs(c->y - b->y)<EPSILON)
  385.                         ||
  386.                         (fabs(a->y - d->y)<EPSILON && fabs(d->y - b->y)<EPSILON))
  387.                     return GLU_TESS_ERROR4;
  388.  
  389.                 }
  390.                 else
  391.                 {
  392.                     if((fabs(b->y - c->y)<EPSILON && fabs(c->y - a->y)<EPSILON)
  393.                         ||
  394.                         (fabs(b->y - d->y)<EPSILON && fabs(d->y - a->y)<EPSILON))
  395.                     return GLU_TESS_ERROR4;
  396.                 }
  397.             }
  398.             else
  399.             {
  400.                 /* compare the X coordinate */
  401.                 if(xba > 0.0)
  402.                 {
  403.                     if((fabs(a->x - c->x)<EPSILON && fabs(c->x - b->x)<EPSILON)
  404.                         ||
  405.                         (fabs(a->x - d->x)<EPSILON && fabs(d->x - b->x)<EPSILON))
  406.                     return GLU_TESS_ERROR4;
  407.                 }
  408.                 else
  409.                 {
  410.                     if((fabs(b->x - c->x)<EPSILON && fabs(c->x - a->x)<EPSILON)
  411.                         ||
  412.                         (fabs(b->x - d->x)<EPSILON && fabs(d->x - a->x)<EPSILON))
  413.                     return GLU_TESS_ERROR4;
  414.                 }
  415.             }
  416.         }
  417.         return GLU_NO_ERROR;
  418.     }
  419.     r /= denom;
  420.     s = (yac*xba - xac*yba) / denom;
  421.     /* test if one vertex lies on other edge */
  422.     if(((fabs(r) < EPSILON || (r < 1.0+EPSILON && r > 1.0-EPSILON)) &&
  423.         s > -EPSILON && s < 1.0+EPSILON) ||
  424.         ((fabs(s) < EPSILON || (s < 1.0+EPSILON && s > 1.0-EPSILON)) &&
  425.         r > -EPSILON && r < 1.0+EPSILON))
  426.     {
  427.         return GLU_TESS_ERROR4;
  428.     }
  429.     /* test for crossing */
  430.     if(r > -EPSILON && r < 1.0+EPSILON &&
  431.         s > -EPSILON && s < 1.0+EPSILON)
  432.     {
  433.         return GLU_TESS_ERROR8;
  434.     }
  435.     return GLU_NO_ERROR;
  436. }
  437.  
  438. static GLUenum verify_edge_vertex_intersections(GLUtriangulatorObj *tobj)
  439. {
  440.     tess_polygon *polygon=tobj->current_polygon;
  441.     tess_vertex *vertex1,*last_vertex,*vertex2;
  442.     GLUenum test;
  443.  
  444.     last_vertex=polygon->last_vertex;
  445.     vertex1=last_vertex;
  446.     for(vertex2=vertex1->next->next;
  447.         vertex2->next!=last_vertex;
  448.         vertex2=vertex2->next)
  449.     {
  450.         test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  451.             vertex2->next);
  452.         if(test!=GLU_NO_ERROR)
  453.         {
  454.             tess_call_user_error(tobj,test);
  455.             return GLU_ERROR;
  456.         }
  457.     }
  458.     for(vertex1=polygon->vertices;
  459.         vertex1->next->next!=last_vertex;
  460.         vertex1=vertex1->next)
  461.     {
  462.         for(vertex2=vertex1->next->next;
  463.             vertex2!=last_vertex;
  464.             vertex2=vertex2->next)
  465.         {
  466.             test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  467.                 vertex2->next);
  468.             if(test!=GLU_NO_ERROR)
  469.             {
  470.                 tess_call_user_error(tobj,test);
  471.                 return GLU_ERROR;
  472.             }
  473.         }
  474.     }
  475.     return GLU_NO_ERROR;
  476. }
  477.  
  478. static int area_compare(const void *a,const void *b)
  479. {
  480.     GLdouble area1,area2;
  481.  
  482.     area1=(*((tess_contour **)a))->area;
  483.     area2=(*((tess_contour **)b))->area;
  484.     if(area1 < area2)
  485.         return 1;
  486.     if(area1 > area2)
  487.         return -1;
  488.     return 0;
  489. }
  490.  
  491. void tess_find_contour_hierarchies(GLUtriangulatorObj *tobj)
  492. {
  493.     tess_contour **contours; /* dinamic array of pointers */
  494.     tess_contour *tmp_contour_ptr=tobj->contours;
  495.     GLuint cnt,i;
  496.     GLUenum result;
  497.     GLboolean hierarchy_changed;
  498.  
  499.     /* any contours? */
  500.     if(tobj->contour_cnt < 2)
  501.     {
  502.         tobj->contours->type=GLU_EXTERIOR;
  503.         return;
  504.     }
  505.     if((contours=(tess_contour **)
  506.         malloc(sizeof(tess_contour *)*(tobj->contour_cnt)))==NULL)
  507.     {
  508.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  509.         return;
  510.     }
  511.     for(tmp_contour_ptr=tobj->contours , cnt=0;
  512.         tmp_contour_ptr!=NULL;
  513.         tmp_contour_ptr=tmp_contour_ptr->next)
  514.         contours[cnt++]=tmp_contour_ptr;
  515.     /* now sort the contours in decreasing area size order */
  516.     qsort((void *)contours,(size_t)cnt,(size_t)sizeof(tess_contour *),&area_compare);
  517.     /* we leave just the first contour - remove others from list */
  518.     tobj->contours=contours[0];
  519.     tobj->contours->next=tobj->contours->previous=NULL;
  520.     tobj->last_contour=tobj->contours;
  521.     tobj->contour_cnt=1;
  522.     /* first contour is the one with greatest area */
  523.     /* must be EXTERIOR */
  524.     tobj->contours->type=GLU_EXTERIOR;
  525.     tmp_contour_ptr=tobj->contours;
  526.     /* now we play! */
  527.     for(i=1;i<cnt;i++)
  528.     {
  529.         hierarchy_changed=GL_FALSE;
  530.         for(tmp_contour_ptr=tobj->contours;
  531.             tmp_contour_ptr!=NULL;
  532.             tmp_contour_ptr=tmp_contour_ptr->next)
  533.         {
  534.             if(tmp_contour_ptr->type==GLU_EXTERIOR)
  535.             {
  536.                 /* check if contour completely contained in EXTERIOR */
  537.                 result=is_contour_contained_in(tmp_contour_ptr,contours[i]);
  538.                 switch(result)
  539.                 {
  540.                     case GLU_INTERIOR:
  541.                         /* now we have to check if contour is inside interiors */
  542.                         /* or not */
  543.                         /* any interiors? */
  544.                         if(tmp_contour_ptr->next!=NULL &&
  545.                             tmp_contour_ptr->next->type==GLU_INTERIOR)
  546.                         {
  547.                             /* for all interior, check if inside any of them */
  548.                             /* if not inside any of interiors, its another */
  549.                             /* interior */
  550.                             /* or it may contain some interiors, then change */
  551.                             /* the contained interiors to exterior ones */
  552.                             add_interior_with_hierarchy_check(tobj,
  553.                                 tmp_contour_ptr,contours[i]);
  554.                         }
  555.                         else
  556.                         {
  557.                             /* not in interior, add as new interior contour */
  558.                             add_new_interior(tobj,tmp_contour_ptr,contours[i]);
  559.                         }
  560.                         hierarchy_changed=GL_TRUE;
  561.                         break;
  562.                     case GLU_EXTERIOR:
  563.                         /* ooops, the marked as EXTERIOR (contours[i]) is */
  564.                         /* actually an interior of tmp_contour_ptr */
  565.                         /*  reverse the local hierarchy */
  566.                         reverse_hierarchy_and_add_exterior(tobj,tmp_contour_ptr,
  567.                             contours[i]);
  568.                         hierarchy_changed=GL_TRUE;
  569.                         break;
  570.                     case GLU_NO_ERROR:
  571.                         break;
  572.                 }
  573.             }
  574.             if(hierarchy_changed)
  575.                 break; /* break from for loop */
  576.         }
  577.         if(hierarchy_changed==GL_FALSE)
  578.         {
  579.             /* disjoint with all contours, add to contour list */
  580.             add_new_exterior(tobj,contours[i]);
  581.         }
  582.     }
  583.     free(contours);
  584. }
  585.  
  586. /* returns GLU_INTERIOR if inner is completey enclosed within outer */
  587. /* returns GLU_EXTERIOR if outer is completely enclosed within inner */
  588. /* returns GLU_NO_ERROR if contours are disjoint */
  589. static GLUenum is_contour_contained_in(
  590.     tess_contour *outer,
  591.     tess_contour *inner)
  592. {
  593.     GLUenum relation_flag;
  594.  
  595.     /* set relation_flag to relation of containment of first inner vertex */
  596.     /* regarding outer contour */
  597.     if(point_in_polygon(outer,inner->vertices->x,inner->vertices->y))
  598.         relation_flag=GLU_INTERIOR;
  599.     else
  600.         relation_flag=GLU_EXTERIOR;
  601.     if(relation_flag==GLU_INTERIOR)
  602.         return GLU_INTERIOR;
  603.     if(point_in_polygon(inner,outer->vertices->x,outer->vertices->y))
  604.         return GLU_EXTERIOR;
  605.     return GLU_NO_ERROR;
  606. }
  607.  
  608. static GLboolean point_in_polygon(
  609.     tess_contour *contour,
  610.     GLdouble x,
  611.     GLdouble y)
  612. {
  613.     tess_vertex *v1,*v2;
  614.     GLuint i,vertex_cnt;
  615.     GLdouble xp1,yp1,xp2,yp2;
  616.     GLboolean tst;
  617.  
  618.     tst=GL_FALSE;
  619.     v1=contour->vertices;
  620.     v2=contour->vertices->previous;
  621.     for(i=0 , vertex_cnt=contour->vertex_cnt;
  622.         i < vertex_cnt;
  623.         i++)
  624.     {
  625.         xp1=v1->x;
  626.         yp1=v1->y;
  627.         xp2=v2->x;
  628.         yp2=v2->y;
  629.         if ((((yp1<=y) && (y<yp2)) || ((yp2<=y)  && (y<yp1))) &&
  630.             (x < (xp2 - xp1) * (y - yp1) /  (yp2 - yp1) + xp1))
  631.                 tst = (tst==GL_FALSE ? GL_TRUE : GL_FALSE);
  632.         v2=v1;
  633.         v1=v1->next;
  634.     }
  635.     return tst;
  636. }
  637.  
  638. static GLUenum contours_overlap(
  639.     tess_contour *contour,
  640.     tess_polygon *polygon)
  641. {
  642.     tess_vertex *vertex1,*vertex2;
  643.     GLuint vertex1_cnt,vertex2_cnt,i,j;
  644.     GLUenum test;
  645.  
  646.     vertex1=contour->vertices;
  647.     vertex2=polygon->vertices;
  648.     vertex1_cnt=contour->vertex_cnt;
  649.     vertex2_cnt=polygon->vertex_cnt;
  650.     for(i=0; i<vertex1_cnt; vertex1=vertex1->next , i++)
  651.     {
  652.         for(j=0; j<vertex2_cnt; vertex2=vertex2->next , j++)
  653.             if((test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  654.                 vertex2->next))!=GLU_NO_ERROR)
  655.                 return test;
  656.     }
  657.     return GLU_NO_ERROR;
  658. }
  659.  
  660. static void add_new_exterior(
  661.     GLUtriangulatorObj *tobj,
  662.     tess_contour *contour)
  663. {
  664.     contour->type=GLU_EXTERIOR;
  665.     contour->next=NULL;
  666.     contour->previous=tobj->last_contour;
  667.     tobj->last_contour->next=contour;
  668.     tobj->last_contour=contour;
  669. }
  670.  
  671. static void add_new_interior(
  672.     GLUtriangulatorObj *tobj,
  673.     tess_contour *outer,
  674.     tess_contour *contour)
  675. {
  676.     contour->type=GLU_INTERIOR;
  677.     contour->next=outer->next;
  678.     contour->previous=outer;
  679.     if(outer->next!=NULL)
  680.         outer->next->previous=contour;
  681.     outer->next=contour;
  682.     if(tobj->last_contour==outer)
  683.         tobj->last_contour=contour;
  684. }
  685.  
  686. static void add_interior_with_hierarchy_check(
  687.     GLUtriangulatorObj *tobj,
  688.     tess_contour *outer,
  689.     tess_contour *contour)
  690. {
  691.     tess_contour *ptr;
  692.  
  693.     /* for all interiors of outer check if they are interior of contour */
  694.     /* if so, change that interior to exterior and move it of of the */
  695.     /* interior sequence */
  696.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  697.     {
  698.         GLUenum test;
  699.  
  700.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  701.         {
  702.             test=is_contour_contained_in(ptr,contour);
  703.             switch(test)
  704.             {
  705.                 case GLU_INTERIOR:
  706.                     /* contour is contained in one of the interiors */
  707.                     /* check if possibly contained in other exteriors */
  708.                     /* move ptr to first EXTERIOR */
  709.                     for(;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next);
  710.                     if(ptr==NULL)
  711.                         /* another exterior */
  712.                         add_new_exterior(tobj,contour);
  713.                     else
  714.                         add_exterior_with_check(tobj,ptr,contour);
  715.                     return;
  716.                 case GLU_EXTERIOR:
  717.                     /* one of the interiors is contained in the contour */
  718.                     /* change it to EXTERIOR, and shift it away from the */
  719.                     /* interior sequence */
  720.                     shift_interior_to_exterior(tobj,ptr);
  721.                     break;
  722.                 case GLU_NO_ERROR:
  723.                     /* disjoint */
  724.                     break;
  725.             }
  726.         }
  727.     }
  728.     /* add contour to the interior sequence */
  729.     add_new_interior(tobj,outer,contour);
  730. }
  731.  
  732. static void reverse_hierarchy_and_add_exterior(
  733.     GLUtriangulatorObj *tobj,
  734.     tess_contour *outer,
  735.     tess_contour *contour)
  736. {
  737.     tess_contour *ptr;
  738.  
  739.     /* reverse INTERIORS to EXTERIORS */
  740.     /* any INTERIORS? */
  741.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  742.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  743.             ptr->type=GLU_EXTERIOR;
  744.     /* the outer now becomes inner */
  745.     outer->type=GLU_INTERIOR;
  746.     /* contour is the EXTERIOR */
  747.     contour->next=outer;
  748.     if(tobj->contours==outer)
  749.     {
  750.         /* first contour beeing reversed */
  751.         contour->previous=NULL;
  752.         tobj->contours=contour;
  753.     }
  754.     else
  755.     {
  756.         outer->previous->next=contour;
  757.         contour->previous=outer->previous;
  758.     }
  759.     outer->previous=contour;
  760. }
  761.  
  762. static void shift_interior_to_exterior(
  763.     GLUtriangulatorObj *tobj,
  764.     tess_contour *contour)
  765. {
  766.     contour->previous->next=contour->next;
  767.     if(contour->next!=NULL)
  768.         contour->next->previous=contour->previous;
  769.     else
  770.         tobj->last_contour=contour->previous;
  771. }
  772.  
  773. static void add_exterior_with_check(
  774.     GLUtriangulatorObj *tobj,
  775.     tess_contour *outer,
  776.     tess_contour *contour)
  777. {
  778.     GLUenum test;
  779.  
  780.     /* this contour might be interior to further exteriors - check */
  781.     /* if not, just add as a new exterior */
  782.     for(;outer!=NULL && outer->type==GLU_EXTERIOR;outer=outer->next)
  783.     {
  784.         test=is_contour_contained_in(outer,contour);
  785.         switch(test)
  786.         {
  787.             case GLU_INTERIOR:
  788.                 /* now we have to check if contour is inside interiors */
  789.                 /* or not */
  790.                 /* any interiors? */
  791.                 if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  792.                 {
  793.                     /* for all interior, check if inside any of them */
  794.                     /* if not inside any of interiors, its another */
  795.                     /* interior */
  796.                     /* or it may contain some interiors, then change */
  797.                     /* the contained interiors to exterior ones */
  798.                     add_interior_with_hierarchy_check(tobj,
  799.                         outer,contour);
  800.                 }
  801.                 else
  802.                 {
  803.                     /* not in interior, add as new interior contour */
  804.                     add_new_interior(tobj,outer,contour);
  805.                 }
  806.                 return;
  807.             case GLU_NO_ERROR:
  808.                 /* disjoint */
  809.                 break;
  810.         }
  811.     }
  812.     /* add contour to the exterior sequence */
  813.     add_new_exterior(tobj,contour);
  814. }
  815.  
  816. void tess_handle_holes(GLUtriangulatorObj *tobj)
  817. {
  818.     tess_contour *contour,*hole;
  819.     GLUenum exterior_orientation;
  820.  
  821.     /* verify hole orientation */
  822.     for(contour=tobj->contours;contour!=NULL;)
  823.     {
  824.         exterior_orientation=contour->orientation;
  825.         for(contour=contour->next;
  826.             contour!=NULL && contour->type==GLU_INTERIOR;
  827.             contour=contour->next)
  828.         {
  829.             if(contour->orientation==exterior_orientation)
  830.             {
  831.                 tess_call_user_error(tobj,GLU_TESS_ERROR5);
  832.                 return;
  833.             }
  834.         }
  835.     }
  836.     /* now cut-out holes */
  837.     for(contour=tobj->contours;contour!=NULL;)
  838.     {
  839.         hole=contour->next;
  840.         while(hole!=NULL && hole->type==GLU_INTERIOR)
  841.         {
  842.             if(cut_out_hole(tobj,contour,hole)==GLU_ERROR)
  843.                 return;
  844.             hole=contour->next;
  845.         }
  846.         contour=contour->next;
  847.     }
  848. }
  849.  
  850. static GLUenum cut_out_hole(
  851.     GLUtriangulatorObj *tobj,
  852.     tess_contour *contour,
  853.     tess_contour *hole)
  854. {
  855.     tess_contour *tmp_hole;
  856.     tess_vertex *v1,*v2,*tmp_vertex;
  857.     GLuint vertex1_cnt,vertex2_cnt,tmp_vertex_cnt;
  858.     GLuint i,j,k;
  859.     GLUenum test;
  860.  
  861.     /* find an edge connecting contour and hole not intersecting any other */
  862.     /* edge belonging to either the contour or any of the other holes */
  863.     for(v1=contour->vertices , vertex1_cnt=contour->vertex_cnt , i=0;
  864.         i<vertex1_cnt;
  865.         i++ , v1=v1->next)
  866.     {
  867.         for(v2=hole->vertices , vertex2_cnt=hole->vertex_cnt , j=0;
  868.             j<vertex2_cnt;
  869.             j++ , v2=v2->next)
  870.         {
  871.             /* does edge (v1,v2) intersect any edge of contour */
  872.             for(tmp_vertex=contour->vertices , tmp_vertex_cnt=contour->vertex_cnt ,
  873.                     k=0;
  874.                 k<tmp_vertex_cnt;
  875.                 tmp_vertex=tmp_vertex->next , k++)
  876.             {
  877.                 /* skip edge tests for edges directly connected */
  878.                 if(v1==tmp_vertex || v1==tmp_vertex->next)
  879.                     continue;
  880.                 test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  881.                 if(test!=GLU_NO_ERROR)
  882.                     break;
  883.             }
  884.             if(test==GLU_NO_ERROR)
  885.             {
  886.                 /* does edge (v1,v2) intersect any edge of hole */
  887.                 for(tmp_vertex=hole->vertices ,
  888.                         tmp_vertex_cnt=hole->vertex_cnt , k=0;
  889.                     k<tmp_vertex_cnt;
  890.                     tmp_vertex=tmp_vertex->next , k++)
  891.                 {
  892.                     /* skip edge tests for edges directly connected */
  893.                     if(v2==tmp_vertex || v2==tmp_vertex->next)
  894.                         continue;
  895.                     test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  896.                     if(test!=GLU_NO_ERROR)
  897.                         break;
  898.                 }
  899.                 if(test==GLU_NO_ERROR)
  900.                 {
  901.                     /* does edge (v1,v2) intersect any other hole? */
  902.                     for(tmp_hole=hole->next;
  903.                         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  904.                         tmp_hole=tmp_hole->next)
  905.                     {
  906.                         /* does edge (v1,v2) intersect any edge of hole */
  907.                         for(tmp_vertex=tmp_hole->vertices ,
  908.                                 tmp_vertex_cnt=tmp_hole->vertex_cnt , k=0;
  909.                             k<tmp_vertex_cnt;
  910.                             tmp_vertex=tmp_vertex->next , k++)
  911.                         {
  912.                             test=edge_edge_intersect(v1,v2,tmp_vertex,
  913.                                 tmp_vertex->next);
  914.                             if(test!=GLU_NO_ERROR)
  915.                                 break;
  916.                         }
  917.                         if(test!=GLU_NO_ERROR)
  918.                             break;
  919.                     }
  920.                 }
  921.             }
  922.             if(test==GLU_NO_ERROR)
  923.             {
  924.                 /* edge (v1,v2) is good for eliminating the hole */
  925.                 if(merge_hole_with_contour(tobj,contour,hole,v1,v2)
  926.                     ==GLU_NO_ERROR)
  927.                     return GLU_NO_ERROR;
  928.                 else
  929.                     return GLU_ERROR;
  930.             }
  931.         }
  932.     }
  933.     /* other holes are blocking all possible connections of hole */
  934.     /* with contour, we shift this hole as the last hole and retry */
  935.     for(tmp_hole=hole;
  936.         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  937.         tmp_hole=tmp_hole->next);
  938.     contour->next=hole->next;
  939.     hole->next->previous=contour;
  940.     if(tmp_hole==NULL)
  941.     {
  942.         /* last EXTERIOR contour, shift hole as last contour */
  943.         hole->next=NULL;
  944.         hole->previous=tobj->last_contour;
  945.         tobj->last_contour->next=hole;
  946.         tobj->last_contour=hole;
  947.     }
  948.     else
  949.     {
  950.         tmp_hole->previous->next=hole;
  951.         hole->previous=tmp_hole->previous;
  952.         tmp_hole->previous=hole;
  953.         hole->next=tmp_hole;
  954.     }
  955.     hole=contour->next;
  956.     /* try once again - recurse */
  957.     return cut_out_hole(tobj,contour,hole);
  958. }
  959.  
  960. static GLUenum merge_hole_with_contour(
  961.     GLUtriangulatorObj *tobj,
  962.     tess_contour *contour,
  963.     tess_contour *hole,
  964.     tess_vertex *v1,
  965.     tess_vertex *v2)
  966. {
  967.     tess_vertex *v1_new,*v2_new;
  968.  
  969.     /* make copies of v1 and v2, place them respectively after their originals */
  970.     if((v1_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  971.     {
  972.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  973.         return GLU_ERROR;
  974.     }
  975.     if((v2_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  976.     {
  977.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  978.         return GLU_ERROR;
  979.     }
  980.     v1_new->edge_flag=GL_TRUE;
  981.     v1_new->data=v1->data;
  982.     v1_new->location[0]=v1->location[0];
  983.     v1_new->location[1]=v1->location[1];
  984.     v1_new->location[2]=v1->location[2];
  985.     v1_new->x=v1->x;
  986.     v1_new->y=v1->y;
  987.     v1_new->shadow_vertex=v1;
  988.     v1->shadow_vertex=v1_new;
  989.     v1_new->next=v1->next;
  990.     v1_new->previous=v1;
  991.     v1->next->previous=v1_new;
  992.     v1->next=v1_new;
  993.     v2_new->edge_flag=GL_TRUE;
  994.     v2_new->data=v2->data;
  995.     v2_new->location[0]=v2->location[0];
  996.     v2_new->location[1]=v2->location[1];
  997.     v2_new->location[2]=v2->location[2];
  998.     v2_new->x=v2->x;
  999.     v2_new->y=v2->y;
  1000.     v2_new->shadow_vertex=v2;
  1001.     v2->shadow_vertex=v2_new;
  1002.     v2_new->next=v2->next;
  1003.     v2_new->previous=v2;
  1004.     v2->next->previous=v2_new;
  1005.     v2->next=v2_new;
  1006.     /* link together the two lists */
  1007.     v1->next=v2_new;
  1008.     v2_new->previous=v1;
  1009.     v2->next=v1_new;
  1010.     v1_new->previous=v2;
  1011.     /* update the vertex count of the contour */
  1012.     contour->vertex_cnt += hole->vertex_cnt+2;
  1013.     /* remove the INTERIOR contour */
  1014.     contour->next=hole->next;
  1015.     if(hole->next!=NULL)
  1016.         hole->next->previous=contour;
  1017.     free(hole);
  1018.     /* update tobj structure */
  1019.     --(tobj->contour_cnt);
  1020.     if(contour->last_vertex==v1)
  1021.         contour->last_vertex=v1_new;
  1022.     /* mark two vertices with edge_flag */
  1023.     v2->edge_flag=GL_FALSE;
  1024.     v1->edge_flag=GL_FALSE;
  1025.     return GLU_NO_ERROR;
  1026. }
  1027.